package A2014;


/*
 对于给定的整数 n 和 m，我们希望求出：
    f(1) + f(2) + ... + f(n)  的值。但这个值可能非常大，所以我们把它对 f(m) 取模。
    但这个数字依然很大，所以需要再对 p 求模。
【数据格式】
输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
输出为1个整数
例如，如果输入：
2 3 5
程序应该输出：
0
再例如，输入：
15 11 29
程序应该输出：
25
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 2000ms
 */
import java.util.Scanner;
public class _9_斐波那契矩阵求解 {//这种解法只能得到60分
	private static long MOD;
	private static long n;
	private static long m;
	private static long mMOD;// f(m)的值

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);// n m p,0 < n, m, p < 10^18
		n = sc.nextLong();
		m = sc.nextLong();
		MOD = sc.nextLong();
		long[][] fa = { { 1, 1 }, { 1, 0 } };// 斐波那契要乘的矩阵
		long[][] fb = { { 1, 1 }, { 0, 0 } };// [f(2),f(1)]的矩阵
		long A =System.currentTimeMillis();
		if (m > n + 2) {
			long[][] fn_2 = twoMatrixPlus(matrixPower(fa, n + 1), fb);// 斐波那契的前n项和为f(n+2)-1,即Σf(n)=f(n+2)-1
			long fn = fn_2[0][0] - 1;
			System.out.println(fn);
			return;
		}
		long[][] fm = twoMatrixPlus(matrixPower(fa, m - 1), fb);
		mMOD = fm[0][0];
		long[][] fn_2 = twoMatrixPlus(matrixPower(fa, n + 1), fb);
		long fn = fn_2[0][0] % mMOD % MOD - 1;
		long B =System.currentTimeMillis();
		System.out.println("运行时间为"+(B-A)+"ms");
		System.out.println(fn);
	}

	public static long[][] matrixPower(long a[][], long l) {
		long ans[][] = new long[a.length][a[0].length];
		for (int i = 0; i < ans.length; i++)
			for (int j = 0; j < ans[0].length; j++) {
				if (i == j)
					ans[i][j] = 1;
				else
					ans[i][j] = 0;
			} // 初始化为单位矩阵
		while (l != 0) {
			if ((l & 1) == 1)
				ans = twoMatrixPlus(ans, a);
			a = twoMatrixPlus(a, a);
			l = l >> 1;
		}
		return ans;
	}

	public static long[][] twoMatrixPlus(long x[][], long y[][]) {// 两个矩阵相乘,具有普适性
		long ans[][] = new long[x.length][y[0].length];
		for (int i = 0; i < ans.length; i++)
			for (int j = 0; j < ans[0].length; j++) {
				ans[i][j] = 0;
			} // 初始化
		for (int i = 0; i < x.length; i++)
			for (int j = 0; j < y[0].length; j++)
				for (int p = 0; p < x[0].length; p++) {
					ans[i][j] += x[i][p] * y[p][j];
					if (m > n + 2) {// 判断f(m)要不要求余f(n+2)-1
						ans[i][j] %= MOD;
					}
				}
		return ans;

	}
}
